package com.echo.boot.leetcode.二叉树;

/**
 * Created with IntelliJ IDEA
 * Created By CQ
 * Date: 2020/5/11
 * Time: 10:17
 */
public class T_CompleteBinaryTree {
    // 如皋一棵完全二叉树有768个节点,求子叶节点个数。
    // n = n0+n1+n2
    // n0=n2+1
    // n2= n0-1
    // n=n0+n1+n0-1
    // n=2n0+n1-1;
    // 一棵完全二叉树的 n1 的节点要么 是 0 或者 1
    // 如果 n1 = 0; n = 2n0 + 0 - 1; n0 = (n+1)/2;n 必然是奇数;非叶子节点 n1+n2=(n-1)/2;
    // 如果 n1 = 1; n = 2n0 + 1 - 1; n0 = n/2; n 必然是偶数;非叶子节点也为 n/2


    // n 如果是偶数 n0 = n/2
    // n 如果是奇数 n0 = (n+1)/2; n0 = n/2 ＋ 1/2;
    // 这里全部用第二个公式 n0 = (n+1)/2; 向下取整。
    // 或者全部用第一种公司 n0 = n/2;  向上取整。

    //代码输出 (n+1) >> 1
    // 代码默认向下取整.
    // floor((n+1)/2)
    // 代码默认向上取整.
    // ceiling(n/2);


    // 叶子节点数: n0 = floor((n+1)/2) 或者 ceiling(n/2);
    // 非叶子节点数: n1+n2 = floor(n/2) 或者 ceiling((n-1)/2);


}
